package com.modular.Shortest_path;

import java.util.*;

public class LC743 {
    public static void main(String[] args) {
        int n = 4,k = 2;
        int [][] times = new int[][]{{2,1,1},{2,3,1},{3,4,1}};
        int network = new Solution7342().network(times, n, k);
        System.out.println(network);

    }
}

//地杰斯特拉模板
class Solution7342 {
    Map<Integer, Integer> dist;//key为到某节点 value 为到某节点的最短路径

    public int network(int[][] times, int N, int K){
        Map<Integer,ArrayList<int[]>> graph = new HashMap<>();
        //处理times
        for (int[] time : times) {
            if(!graph.containsKey(time[0]))
                graph.put(time[0],new ArrayList<int []>());
            graph.get(time[0]).add(new int[]{time[1],time[2]});
        }

        //距离
        int []dist = new int[N+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        //是否访问过
        boolean []visit = new boolean[N+1];

        //起点的dis为0，但是别忘记0也要搞一下，因为它是不参与的，我计算结果的时候直接用了stream，所以这个0也就要初始化下了
        dist[K] = 0;
        dist[0] = 0;

        //  new一个小堆出来，按照dis升序排，一定要让它从小到大排，省去了松弛工作
        PriorityQueue<Integer> queue = new  PriorityQueue<>((o1, o2) -> dist[o1] - dist[o2]);
        queue.offer(K);
        while(!queue.isEmpty()){
            int nowindex = queue.poll();//获取当前的index
            if(visit[nowindex]) continue;
            visit[nowindex] = true;
            ArrayList<int[]> ints = graph.get(nowindex);
            if(ints == null) continue;
            for (int[] anInt : ints) {
                int next = anInt[0];

                if(visit[next]) continue;//已经访问过了
                dist[next] =  Math.min(dist[next], dist[nowindex] + anInt[1]);
                queue.offer(next);
            }
        }
        int ans = 0;
        for (int cand:dist) {
            if (cand == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, cand);
        }
        return ans;

    }
    public int networkDelayTime(int[][] times, int N, int K) {
        //key为节点 List为时间和目的节点
        Map<Integer, List<int[]>> graph = new HashMap();
        for (int[] edge: times) {
            if (!graph.containsKey(edge[0]))
                graph.put(edge[0], new ArrayList<int[]>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});//edge[1]为目的节点
        }
        dist = new HashMap();
        //所有节点的dist初始化为最大值
        for (int node = 1; node <= N; ++node)
            dist.put(node, Integer.MAX_VALUE);

        dist.put(K, 0);

        boolean[] seen = new boolean[N+1];

        while (true) {
            int candNode = -1;
            int candDist = Integer.MAX_VALUE;
            for (int i = 1; i <= N; ++i) {
                //在所有还未确定最短路径的节点中 寻找到起始点距离最小的点
                if (!seen[i] && dist.get(i) < candDist) {
                    candDist = dist.get(i);//路径长度
                    candNode = i;//节点
                }
            }

            if (candNode < 0) break;//没有找到最小点
            seen[candNode] = true;//已经访问过了
            //用当前candNode去更新其他的节点的路径情况
            if (graph.containsKey(candNode))
                for (int[] info: graph.get(candNode))
                    dist.put(info[0],
                            Math.min(dist.get(info[0]), dist.get(candNode) + info[1]));
        }

        int ans = 0;
        for (int cand: dist.values()) {
            if (cand == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, cand);
        }
        return ans;
    }
}



//Bellman-Ford
class Solution7343{
    public int findShortestPath (int n, int m, int[][] graph) {
        // write code here
        int[] dp = new int[n+1];
        for(int i=0;i<=n;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        dp[1] = 0;
        for(int i=1; i<n-1; i++){
            //int min = Integer.MAX_VALUE;
            for(int []graph1:graph){
                int u = graph1[0];
                int v = graph1[1];
                int time = graph1[2];
                if(dp[u]!=Integer.MAX_VALUE){
                    if(dp[v] == Integer.MAX_VALUE){
                        dp[v] = dp[u]+time;
                    }else{
                        dp[v] = Math.min(dp[v],dp[u]+time);
                    }
                }
//                if(graph[j][1] == i && dp[graph[j][0]] != -1){
//                    dp[] = Math.min(min,graph[j][2]+dp[graph[j][0]]);
//                }
            }
        }
//        int ans = 0;
//        for (int i=1;i<=n;i++) {
//            if (dp[i] == Integer.MAX_VALUE) return -1;
//            ans = Math.max(ans, dp[i]);
//        }
//        return ans;
        return dp[n]==Integer.MAX_VALUE?-1:dp[n];
        //return dp[n];
    }
    public int networkDelayTime(int[][] times, int n, int k) {
        int []dist = new int[n+1];
        for(int i=0;i<=n;i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[k] =0;
        for(int i=1;i<=n-1;i++){
            for (int[] time : times) {
                // 源节点
                int u = time[0];
                // 目标节点
                int v = time[1];
                // 一个信号源从源节点到目标节点的时间
                int w = time[2];
                // 判断能否通过 u->v 缩短 distance[v]（松弛）
                if (dist[u] != Integer.MAX_VALUE) {
                    if (dist[v] == Integer.MAX_VALUE) {//说明还没更新
                        dist[v] = dist[u] + w;
                    } else {//说明v节点已经有值了，需要找最短路径来更新他
                        dist[v] = Math.min(dist[v], dist[u] + w);
                    }
                }
            }
        }
        int ans = 0;
        for (int i=1;i<=n;i++) {
            if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }

}

class Solution734 {
    Map<Integer, Integer> dist;
    public int networkDelayTime(int[][] times, int N, int K) {
        Map<Integer, List<int[]>> graph = new HashMap();
        for (int[] edge: times) {
            if (!graph.containsKey(edge[0]))
                graph.put(edge[0], new ArrayList<int[]>());
            graph.get(edge[0]).add(new int[]{edge[2], edge[1]});
        }
        for (int node: graph.keySet()) {
            Collections.sort(graph.get(node), (a, b) -> a[0] - b[0]);
        }
        dist = new HashMap();
        for (int node = 1; node <= N; ++node)
            dist.put(node, Integer.MAX_VALUE);

        dfs(graph, K, 0);
        int ans = 0;
        for (int cand: dist.values()) {
            if (cand == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, cand);
        }
        return ans;
    }

    public void dfs(Map<Integer, List<int[]>> graph, int node, int elapsed) {
        if (elapsed >= dist.get(node)) return;
        dist.put(node, elapsed);
        if (graph.containsKey(node))
            for (int[] info: graph.get(node))
                dfs(graph, info[1], elapsed + info[0]);
    }
}
